/**
 * Created with IntelliJ IDEA.
 * Description:
 * https://gitee.com/li--jiaqiang/java-test.git
 * git pull
 * git pull origin master
 * git pull origin master --allow-unrelated-histories
 * User: 86187
 * Date: 2022-05-06
 * Time: 1:07
 */

//Scanner scan = new Scanner(System.in);

import java.util.*;

class Node {
    int val;
    Node next = null;

    Node(int val) {
        this.val = val;
    }
}

public class ListNode1 {

    public Node head = null;

    //尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);

        if(this.head == null) {
            this.head = newNode;
        } else {
            Node pos = this.head;
            while(pos.next != null) {
                pos = pos.next;
            }
            pos.next = newNode;
        }
    }

    //打印方法
    public void display() {
        Node pos = this.head;
        while(pos != null) {
            System.out.print(pos.val+" ");
            pos = pos.next;
        }
        System.out.println();
    }

    public void display2(Node pHead) {
        Node pos = pHead;
        while(pos != null) {
            System.out.print(pos.val+" ");
            pos = pos.next;
        }
        System.out.println();
    }


    //销毁链表
    public void clear() {
        head = null;
    }


    /**
     * 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
     * 且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
     * @param x
     * @return
     */
    public Node partition(int x) {
        // write code here
        if(this.head == null) {
            return null;
        }

        Node bs = null;
        Node be = null;

        Node as = null;
        Node ae = null;
        Node cur = this.head;

        while(cur != null) {
            if(cur.val < x) {
                // 第一次插入
                if(bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                if(as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs == null) {
            return as;
        }

        be.next = as;
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
}